/*
 * @lc app=leetcode.cn id=954 lang=cpp
 *
 * [954] 二倍数对数组
 */

// @lc code=start
class Solution
{
public:
    bool canReorderDoubled(vector<int> &arr)
    {
        unordered_map<int, int> cnt;
        for (int x : arr)
        {
            cnt[x]++;
        }
        if (cnt[0] % 2)
        {

            return false;
        }

        vector<int> vals;
        for (auto &[x, _] : cnt)
        {
            vals.push_back(x);
        }
        sort(vals.begin(), vals.end(), [](int a, int b)
             { return abs(a) < abs(b); });

        for (int x : vals)
        {
            if (cnt[2 * x] < cnt[x])
            {
                return false;
            }
            cnt[2 * x] -= cnt[x];
        }
        return true;
    }
};
// @lc code=end
